package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 郭辉
 * @className TODO
 * @description 70. 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 *
 *
 * 提示：
 *
 * 1 <= n <= 45
 * @date 2023/3/13 14:09
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet70 {
    public int climbStairs(int n) {
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        int result = 0;
        List<Integer> list = new ArrayList<>();
        List<Integer> table = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            table.add(-1);
        }
        list.add(0);
        int i = climbStairsT(n - 1, list,table);
        int i1 = climbStairsT(n - 2, list,table);
        return i + i1;
    }

    private int climbStairsT(int n,List<Integer>  result,List<Integer> table){
        if (table.get(n) != -1){
            return table.get(n);
        }
        int l = 0, r = 0;
        //basecase
        if (n < 0){
            return -1;
        }
        if (n == 2){
            return 2;
        }
        if (n == 1){
            return 1;
        }
        //遍历选择
        l = climbStairsT(n - 1, result,table);
        r = climbStairsT(n - 2, result,table);
        if (l<0){
            l = 0;
        }
        if (r<0){
            r=0;
        }
        result.set(0, l + r);
        table.set(n,l + r);
        return result.get(0);
    }

    public static void main(String[] args) {
        Leet70 leet70 = new Leet70();
        System.out.println(leet70.climbStairs(5));
    }
}
